package leetcode;

import java.util.*;


public class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param str    string字符串一维数组
     * @param target string字符串
     * @return int整型
     */
    public int getMin(String[] str, String target) {
        // 预处理，过滤掉不符合条件的字符串
        List<String> userfulStrs = new ArrayList<>();
        Set<Character> targetChars = new HashSet<>();
        for (char c : target.toCharArray()) {
            targetChars.add(c);
        }

        for (String s : str) {
            if (s.isEmpty()) {
                continue;
            }
            boolean hasUserful = false;
            for (char c : s.toCharArray()) {
                if (targetChars.contains(c)) {
                    hasUserful = true;
                    break;
                }
            }
            if (hasUserful) {
                userfulStrs.add(s);
            }
        }
        if (userfulStrs.isEmpty()) {
            return -1;
        }

        //BFS 寻找覆盖 target 最少字符串的数量

        int n = target.length();
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;
        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++) {
                int start = queue.poll();
                for (String s : userfulStrs) {
                    int maxEnd = start;
                    for (int j = 0; j < s.length() && maxEnd < n; j++) {
                        char c = s.charAt(j);
                        if (c == target.charAt(maxEnd)) {
                            maxEnd++;
                        }
                    }
                    if (maxEnd == n) {
                        return step;
                    }
                    if (!visited[maxEnd]) {
                        visited[maxEnd] = true;
                        queue.offer(maxEnd);
                    }
                }
            }
        }
        return -1;
    }
}